P2303 [SDOI2012] Longge 的问题

发布于 2020-09-12 | 分类于数论、欧拉函数 | 2分钟 | 266字数

\sum_{i=1}^n(i,n)

\sum_{d|n}d\sum_{i=1}^n[(i,n)=d]

P5130 纯粹的弹幕地狱

发布于 2020-09-12 | 分类于数论、莫比乌斯反演 | 6分钟 | 1028字数

因为每回合击中的概率是固定的，所以只需要算一次。概率为：可以击中的情况/总情况。每个点有

(n+1)^2

个位置，所以总情况为

(n+1)^4

发布于 2020-09-12 | 分类于数论 | 3分钟 | 417字数

如果你做过 P4358 [CQOI2016]密钥破解，那么你基本上就凉了。

这道题跟背景没有任何关系。

注意到二元不定方程： $xe1+ye2=(e1,e2)=1$

发布于 2020-09-12 | 分类于树状数组、莫比乌斯反演 | 5分钟 | 758字数

\sum_{i=1}^n\sum_{j=1}^m \sigma((i,j))

\sum_{d=1}^{\min(n,m)}\sigma(d)\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=d]

发布于 2020-09-12 | 分类于数论、欧拉函数 | 1分钟 | 141字数

观察样例可以发现：

发布于 2020-09-12 | 分类于莫比乌斯反演 | 3分钟 | 471字数

这道题的反推还是挺有意思的。

\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor \frac{n}{j} \rfloor}\sum_{q=1}^{\lfloor \frac{n}{j} \rfloor}[(i,j)=1][(p,q)=1]

发布于 2020-09-12 | 分类于树形dp | 4分钟 | 750字数

此题有一个神仙结论：最优链上最多包含一个‘2’，且‘2’不能在链的两边。 至于证明过于简单但很麻烦（~~其实是我懒~~），给大家推荐一个博客，点这。

有了这个结论之后，我们就可以愉快的开始树形dp了。

发布于 2020-09-12 | 6分钟 | 905字数

\sum_{i=1}^n\sum_{j=1}^m ij (i,j)\mu^2((i,j))

\sum_{k=1}^{\min(n,m)}\sum_{i=1}^n\sum_{j=1}^m [(i,j)=k]ij k\mu^2(k)

发布于 2020-09-12 | 分类于莫比乌斯反演 | 5分钟 | 716字数

并不会有更好的阅读体验 ~~甚至你在机房还访问不了~~

\prod_{i=1}^n\prod_{j=1}^m (i,j)

发布于 2020-09-10 | 分类于矩阵乘法、状压dp | 5分钟 | 809字数

你得知道题目下表是从 $0$ 开始编号，那么每个棋子只能控制与它距离不大于 $1$ 的行。

所以只需压当前这一行的状态，令 $dp(i,S)$ 表示前 $i$ 行棋子，第 $i$ 的摆放状态为 $S$ 的方案。

那么有转移：